package first

/*
	请实现一个函数用来匹配包含'. '和'*'的正则表达式。
	模式中的字符'.'表示任意一个字符，
	而'*'表示它前面的字符可以出现任意次（含0次）。
	在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

	示例 1:

	输入:
	s = "aa"
	p = "a"
	输出: false
	解释: "a" 无法匹配 "aa" 整个字符串。
	示例 2:

	输入:
	s = "aa"
	p = "a*"
	输出: true
	解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
	示例3:

	输入:
	s = "ab"
	p = ".*"
	输出: true
	解释:".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
	示例 4:

	输入:
	s = "aab"
	p = "c*a*b"
	输出: true
	解释:因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
	示例 5:

	输入:
	s = "mississippi"
	p = "mis*is*p*."
	输出: false
	s可能为空，且只包含从a-z的小写字母。
	p可能为空，且只包含从a-z的小写字母以及字符.和*，无连续的 '*'。

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/*
	如果模式中的第二个字符不是*、则判断方式如下
	1. 满足p[0]==s[0]或者p[0]==.则s和p都后移一位、继续匹配后面的s和p、否则返回false
	如果模式中的第二个字符是*、有两种选择
	1. 如果p[0]和s[0]不匹配、p直接后移两位、s不变、也就是*前面的字符出现0次
	2. 如果p[0]和s[0]匹配、s后移1位、p不变、因为s后面的的字符可能与s[0]相等
*/
func IsMatch(s string, p string) bool {
	return isMatch(s, p)
}
func isMatch(s string, p string) bool {
	return _isMatch(s, p)
}

func _isMatch(s string, p string) bool {
	if len(p) == 0 {
		return len(s) == 0
	}
	first := len(s)!=0 && (s[0] == p[0] || p[0] == '.')
	if len(p) >= 2 && p[1] == '*' {
		return _isMatch(s, p[2:]) || (first && _isMatch(s[1:], p))
	} else if first {
		return _isMatch(s[1:], p[1:])
	}
	return false
}
